package com.fe.class05;

/**
 * @Description 区间和达标的子数组数量
 * https://leetcode-cn.com/problems/count-of-range-sum/
 * 给你一个整数数组nums 以及两个整数lower 和 upper 。求数组中，区间和的值位于范围 [lower, upper] 之内的个数
 * 区间和S(i, j)表示在nums中，位置从i到j的元素之和，包含i和j(i ≤ j)。
 * @Author sosuke :-)
 * @Date 2021/12/22 05:46
 */
public class Code01_CountOfRangeSum {
    /**
     * 给定一个整数数组arr，以及两个整数lower和upper， 返回arr中有多少个子数组的累加和在[lower,upper]范围上
     * 转化1：区间和S(i, j) = 前缀和S(0, j) - 前缀和S(0, i-1)
     * 根据arr数组求出前缀和数组preSum，所以区间和S(i, j) = preSum[j] - preSum[i-1]
     * preSum[j]可以看做右组的数，preSum[i-1]可以看做左组的数
     * 转化2：目标等价于，求前缀和数组preSum中，对于右组中的每个数X，求左组中有多少个数Y，
     * 位于[X-upper, X-lower]范围上，则 X-Y 就会位于 [lower,upper]范围上
     * 目标：左组和右组都要有序，对于右组的数X，左组的数Y要在 [X-upper, X-lower]范围上
     *
     * @param arr
     * @param lower
     * @param upper
     * @return
     */
    public static int countRangeSum(int[] arr, int lower, int upper) {
        if (null == arr || arr.length == 0) {
            return 0;
        }
        long[] preSum = new long[arr.length]; // arr对应的前缀和数组，这里使用long数组！！
        preSum[0] = arr[0];
        for (int i = 1; i < arr.length; i++) {
            preSum[i] = preSum[i - 1] + arr[i];
        }
        // 转化成求前缀和数组中有多少preSum[j] - preSum[i-1]在[lower,upper]范围上
        return process(preSum, 0, preSum.length - 1, lower, upper);
    }

    private static int process(long[] preSum, int L, int R, int lower, int upper) {
        // base case
        if (L == R) { // 说明此时arr只有一个数据
            return preSum[L] >= lower && preSum[L] <= upper ? 1 : 0;
        }
        int M = L + ((R - L) >> 1);
        // 递归方式
        return process(preSum, L, M, lower, upper) +
                process(preSum, M + 1, R, lower, upper) +
                merge(preSum, L, M, R, lower, upper);
    }

    /**
     * 使用归并排序左右组合并的思想，左右组都是有序的
     * 目标：对于右组的每个数X，求左组有多少个数Y条件：在[X-upper, X-lower]范围上
     */
    private static int merge(long[] preSum, int L, int M, int R, int lower, int upper) {
        int ans = 0;
        int windowL = L;
        int windowR = L;
        // 1. 遍历右组，计算满足条件的左组个数
        // 针对右组的某个数，左组数所要满足的条件范围也是单调递增的，所以windowL、windowR不用回退
        for (int i = M + 1; i <= R; i++) {
            // 左组数要满足的条件范围
            long min = preSum[i] - upper;
            long max = preSum[i] - lower;
            while (windowL <= M && preSum[windowL] < min) {
                windowL++;
            }
            while (windowR <= M && preSum[windowR] <= max) {
                windowR++;
            }
            // 上面条件是preSum[windowR] <= max，表示最终preSum[windowR]不在范围内
            ans += windowR - windowL;
        }

        // 2. 合并左右组，使得数组有序
        long[] help = new long[R - L + 1];
        int i = 0;
        int p1 = L;
        int p2 = M + 1;
        while (p1 <= M && p2 <= R) {
            help[i++] = preSum[p1] < preSum[p2] ? preSum[p1++] : preSum[p2++];
        }
        while (p1 <= M) {
            help[i++] = preSum[p1++];
        }
        while (p2 <= R) {
            help[i++] = preSum[p2++];
        }
        for (int j = 0; j < help.length; j++) {
            preSum[L + j] = help[j];
        }
        return ans;
    }

}
